\section{Изучение универсальных методов сжатия на примере короткого текста}
Задан текст: 
\begin{equation}
    \texttt{<<In\_order\_to\_get\_where\_you\_want\_to\_go,\_you\_first\_have\_to\_leave\_where\_you\_are>>}
\end{equation}

Требуется применить к нему универсальные методы сжатия и сопоставить результаты с некоторыми стандартными архиваторами.

\subsection{Двупроходное кодирование с использованием кода Хаффмена}
Для решения задачи была написана программа, посчитаны вероятности и кодовые слова. Они предоставлены в следующей таблице:

\renewcommand\arraystretch{1.0}
\begin{center}
    \begin{longtable}{|c|c|c|c|}
        \hline
        Буква&Частота буквы в тексте&Длина кодового слова&Кодовое слово \\
        \hline  \_&16&2&00\\  \hline o&8&3&010\\  \hline a&4&4&0110\\  \hline n&2&5&01110\\  \hline g&2&5&01111\\  \hline i&1&6&100000\\  \hline s&1&6&100001\\  \hline ,&1&6&100010\\  \hline I&1&6&100011\\  \hline f&1&6&100100\\  \hline d&1&6&100101\\  \hline y&3&5&10011\\  \hline e&10&3&101\\  \hline t&6&4&1100\\  \hline r&6&4&1101\\  \hline w&3&5&11100\\  \hline u&3&5&11101\\  \hline h&3&5&11110\\  \hline l&1&6&111110\\  \hline v&2&6&111111\\  \hline
    \end{longtable}
\end{center}

В итоге каждый символ текста был закодирован, согласно следующей таблице:
\begin{center}
    \begin{longtable}{|c|c|c|c|c|}
        \hline
        Буква&Вероятность буквы&Длина кодового слова&Кодовое слово&Длина сообщения \\
        \hline  I&1/75&6&111110&6\\  \hline  n&2/75&5&01111&11\\  \hline  \_&16/75&2&00&13\\  \hline  o&8/75&3&010&16\\  \hline  r&2/25&4&1101&20\\  \hline  d&1/75&6&100011&26\\  \hline  e&2/15&3&101&29\\  \hline  r&2/25&4&1101&33\\  \hline  \_&16/75&2&00&35\\  \hline  t&2/25&4&1100&39\\  \hline  o&8/75&3&010&42\\  \hline  \_&16/75&2&00&44\\  \hline  g&2/75&5&01110&49\\  \hline  e&2/15&3&101&52\\  \hline  t&2/25&4&1100&56\\  \hline  \_&16/75&2&00&58\\  \hline  w&1/25&5&10011&63\\  \hline  h&1/25&5&11110&68\\  \hline  e&2/15&3&101&71\\  \hline  r&2/25&4&1101&75\\  \hline  e&2/15&3&101&78\\  \hline  \_&16/75&2&00&80\\  \hline  y&1/25&5&11101&85\\  \hline  o&8/75&3&010&88\\  \hline  u&1/25&5&11100&93\\  \hline  \_&16/75&2&00&95\\  \hline  w&1/25&5&10011&100\\  \hline  a&4/75&4&0110&104\\  \hline  n&2/75&5&01111&109\\  \hline  t&2/25&4&1100&113\\  \hline  \_&16/75&2&00&115\\  \hline  t&2/25&4&1100&119\\  \hline  o&8/75&3&010&122\\  \hline  \_&16/75&2&00&124\\  \hline  g&2/75&5&01110&129\\  \hline  o&8/75&3&010&132\\  \hline  ,&1/75&6&100101&138\\  \hline  \_&16/75&2&00&140\\  \hline  y&1/25&5&11101&145\\  \hline  o&8/75&3&010&148\\  \hline  u&1/25&5&11100&153\\  \hline  \_&16/75&2&00&155\\  \hline  f&1/75&6&100010&161\\  \hline  i&1/75&6&100100&167\\  \hline  r&2/25&4&1101&171\\  \hline  s&1/75&6&100000&177\\  \hline  t&2/25&4&1100&181\\  \hline  \_&16/75&2&00&183\\  \hline  h&1/25&5&11110&188\\  \hline  a&4/75&4&0110&192\\  \hline  v&2/75&6&111111&198\\  \hline  e&2/15&3&101&201\\  \hline  \_&16/75&2&00&203\\  \hline  t&2/25&4&1100&207\\  \hline  o&8/75&3&010&210\\  \hline  \_&16/75&2&00&212\\  \hline  l&1/75&6&100001&218\\  \hline  e&2/15&3&101&221\\  \hline  a&4/75&4&0110&225\\  \hline  v&2/75&6&111111&231\\  \hline  e&2/15&3&101&234\\  \hline  \_&16/75&2&00&236\\  \hline  w&1/25&5&10011&241\\  \hline  h&1/25&5&11110&246\\  \hline  e&2/15&3&101&249\\  \hline  r&2/25&4&1101&253\\  \hline  e&2/15&3&101&256\\  \hline  \_&16/75&2&00&258\\  \hline  y&1/25&5&11101&263\\  \hline  o&8/75&3&010&266\\  \hline  u&1/25&5&11100&271\\  \hline  \_&16/75&2&00&273\\  \hline  a&4/75&4&0110&277\\  \hline  r&2/25&4&1101&281\\  \hline  e&2/15&3&101&284\\  \hline 
    \end{longtable}
\end{center}

В итоге получилось 284 бита на закодированное сообщение, $20 \cdot 8 = 160$ бит на кодовые слова и $20 \cdot 2 - 1 = 39$ бит на дерево Хаффмена. 
В итоге $284 + 160 + 39 = 483$ бита.

\subsection{Арифметическое кодирование}
Для адаптивного арифметического кодирования был использован A-алгоритм:
\begin{equation}
p_n(a) = \begin{cases}
            \frac{\tau_n(a)}{n + 1}, & \text{если $\tau_n(a) > 0$} \\
            \frac{1}{(n + 1) \cdot (M - M_n)}, & \text{если $\tau_n(a) = 0$}
        \end{cases}
\end{equation}
 
 
В следующей таблице приведен результат работы.

\begin{center}
    \begin{longtable}{|c|c|c|}
        \hline
        Буква&Текущая вероятность&G \\
         \hline  I&1/256&0.00390625\\ \hline  n&1/510&7.659313725490196e-06\\ \hline  \_&1/762&1.0051592815603932e-08\\ \hline  o&1/1012&9.932403967988075e-12\\ \hline  r&1/1260&7.882860292054028e-15\\ \hline  d&1/1506&5.234302982771599e-18\\ \hline  e&1/1750&2.991030275869485e-21\\ \hline  r&1/8&3.738787844836856e-22\\ \hline  \_&1/9&4.1542087164853956e-23\\ \hline  t&1/2490&1.668356914251163e-26\\ \hline  o&1/11&1.5166881038646937e-27\\ \hline  \_&1/6&2.527813506441156e-28\\ \hline  g&1/3224&7.840612613030881e-32\\ \hline  e&1/14&5.6004375807363436e-33\\ \hline  t&1/15&3.733625053824229e-34\\ \hline  \_&3/16&7.00054697592043e-35\\ \hline  w&1/4199&1.667193849945327e-38\\ \hline  h&1/4428&3.765117095630821e-42\\ \hline  e&2/19&3.9632811532956006e-43\\ \hline  r&1/10&3.9632811532956e-44\\ \hline  e&1/7&5.661830218993716e-45\\ \hline  \_&2/11&1.0294236761806755e-45\\ \hline  y&1/5635&1.82683882197103e-49\\ \hline  o&1/12&1.5223656849758584e-50\\ \hline  u&1/6100&2.4956814507800957e-54\\ \hline  \_&5/26&4.799387405346338e-55\\ \hline  w&1/27&1.777550890869014e-56\\ \hline  a&1/6804&2.612508657949756e-60\\ \hline  n&1/29&9.008650544654332e-62\\ \hline  t&1/15&6.005767029769554e-63\\ \hline  \_&6/31&1.1624065218908817e-63\\ \hline  t&3/32&1.0897561142727014e-64\\ \hline  o&1/11&9.906873766115467e-66\\ \hline  \_&7/34&2.039650481259067e-66\\ \hline  g&1/35&5.827572803597334e-68\\ \hline  o&1/9&6.475080892885927e-69\\ \hline  ,&1/8954&7.231495301413811e-73\\ \hline  \_&4/19&1.522420063455539e-73\\ \hline  y&1/39&3.9036411883475363e-75\\ \hline  o&1/8&4.8795514854344203e-76\\ \hline  u&1/41&1.1901345086425415e-77\\ \hline  \_&3/14&2.5502882328054463e-78\\ \hline  f&1/10363&2.460955546468635e-82\\ \hline  i&1/10560&2.330450328095298e-86\\ \hline  r&1/15&1.553633552063532e-87\\ \hline  s&1/10994&1.4131649554880228e-91\\ \hline  t&4/47&1.2026935791387425e-92\\ \hline  \_&5/24&2.505611623205714e-93\\ \hline  h&1/49&5.113493108583089e-95\\ \hline  a&1/50&1.022698621716618e-96\\ \hline  v&1/12138&8.425594181221106e-101\\ \hline  e&1/13&6.481226293247005e-102\\ \hline  \_&11/53&1.3451601740701331e-102\\ \hline  t&5/54&1.2455186796945678e-103\\ \hline  o&6/55&1.358747650575892e-104\\ \hline  \_&3/14&2.9116021083769112e-105\\ \hline  l&1/13509&2.155305432213274e-109\\ \hline  e&5/58&1.8580219243217877e-110\\ \hline  a&2/59&6.298379404480636e-112\\ \hline  v&1/60&1.0497299007467727e-113\\ \hline  e&6/61&1.0325212138492846e-114\\ \hline  \_&13/62&2.1649638354904353e-115\\ \hline  w&2/63&6.872901065049002e-117\\ \hline  h&1/32&2.147781582827813e-118\\ \hline  e&7/65&2.312995550737645e-119\\ \hline  r&2/33&1.4018154852955422e-120\\ \hline  e&8/67&1.6738095346812444e-121\\ \hline  \_&7/34&3.4460784537555035e-122\\ \hline  y&2/69&9.988633199291313e-124\\ \hline  o&1/10&9.988633199291313e-125\\ \hline  u&2/71&2.8136994927581164e-126\\ \hline  \_&5/24&5.861873943246077e-127\\ \hline  a&3/73&2.408989291744963e-128\\ \hline  r&5/74&1.6276954673952452e-129\\ \hline  e&3/25&1.953234560874294e-130\\ \hline 

    \end{longtable}
\end{center}

В итоге $G$ примерно равно:
\begin{equation}
\frac1{5119712808851725692816552456016762731640951109900195370850048610818595016807 \cdot 10^{54}}
\end{equation}

Ну и длина кода равна:

\begin{equation}
    l = \lceil -\log G \rceil + 1 = 432
\end{equation}
\newpage
\subsection{Нумерационное кодирование}

\begin{center}
    \begin{longtable}{|c|c|c|}
    \hline
    Буква&Индекс буквы&Количество вхождений буквы в текст \\    
 \hline ,&44&1\\  \hline I&73&1\\  \hline \_&95&16\\  \hline a&97&4\\  \hline d&100&1\\  \hline e&101&10\\  \hline f&102&1\\  \hline g&103&2\\  \hline h&104&3\\  \hline i&105&1\\  \hline l&108&1\\  \hline n&110&2\\  \hline o&111&8\\  \hline r&114&6\\  \hline s&115&1\\  \hline t&116&6\\  \hline u&117&3\\  \hline v&118&2\\  \hline w&119&3\\  \hline y&121&3\\  \hline 
    \end{longtable}
\end{center}

Номер данной композиции равен:
$$
    3397120139502415624975349973851857840183453004248002394366454651971303032576
$$
Длина этого числа в двоичной записи 251 бит. Индекс заданной нам строки в отсортированном в лексикографическом порядке списке всех строк с заданной композицией:
$$
    62825702127366090376149724605382273591532344574336711158549954560000000000
$$
Длина этого числа в двоичной записи 246 бит. И длина сообщения $n = 75$, 7 бит. Итого $251+246+7=504$ бита.
\subsection{Алгоритм LZ-77}
\begin{center}
    \begin{longtable}{|c|c|c|c|c|c|}
    \hline
    Найден&Буква&Расстояние&Длина&Код&Длина кода\\    
 \hline  0&I&---&---&0 01001001&9\\  \hline  0&n&---&---&0 01101110&9\\  \hline  0&\_&---&---&0 01011111&9\\  \hline  0&o&---&---&0 01101111&9\\  \hline  0&r&---&---&0 01110010&9\\  \hline  0&d&---&---&0 01100100&9\\  \hline  0&e&---&---&0 01100101&9\\  \hline  1&r&3&1&1 0000011 0&9\\  \hline  1&\_&6&1&1 0000110 0&9\\  \hline  0&t&---&---&0 01110100&9\\  \hline  1&o&7&1&1 0000111 0&9\\  \hline  1&\_&9&1&1 0001001 0&9\\  \hline  0&g&---&---&0 01100111&9\\  \hline  1&e&7&1&1 0000111 0&9\\  \hline  1&t&5&1&1 0000101 0&9\\  \hline  1&\_&13&1&1 0001101 0&9\\  \hline  0&w&---&---&0 01110111&9\\  \hline  0&h&---&---&0 01101000&9\\  \hline  1&er&12&2&1 0001100 100&11\\  \hline  1&e&14&1&1 0001110 0&9\\  \hline  1&\_&19&1&1 0010011 0&9\\  \hline  0&y&---&---&0 01111001&9\\  \hline  1&o&20&1&1 0010100 0&9\\  \hline  0&u&---&---&0 01110101&9\\  \hline  1&\_w&10&2&1 0001010 100&11\\  \hline  0&a&---&---&0 01100001&9\\  \hline  1&n&27&1&1 0011011 0&9\\  \hline  1&t\_&15&2&1 0001111 100&11\\  \hline  1&to\_g&22&4&1 0010110 101000&14\\  \hline  1&o&32&1&1 0100000 0&9\\  \hline  0&,&---&---&0 00101100&9\\  \hline  1&\_you\_&16&5&1 0010000 101010&14\\  \hline  0&f&---&---&0 01100110&9\\  \hline  0&i&---&---&0 01101001&9\\  \hline  1&r&40&1&1 0101000 0&9\\  \hline  0&s&---&---&0 01110011&9\\  \hline  1&t\_&32&2&1 0100000 100&11\\  \hline  1&h&31&1&1 0011111 0&9\\  \hline  1&a&22&1&1 0010110 0&9\\  \hline  0&v&---&---&0 01110110&9\\  \hline  1&e\_&31&2&1 0011111 100&11\\  \hline  1&to\_&44&3&1 0101100 110&11\\  \hline  0&l&---&---&0 01101100&9\\  \hline  1&e&51&1&1 0110011 0&9\\  \hline  1&ave\_&9&4&1 0001001 101000&14\\  \hline  1&where\_you\_&46&10&1 0101110 1110100&15\\  \hline  1&a&45&1&1 0101101 0&9\\  \hline  1&re&54&2&1 0110110 100&11\\  \hline 
    \end{longtable}
\end{center}

Итого, суммарная длина равна 467 бит.
\subsection{Алгоритм LZW}
\begin{center}
    \begin{longtable}{|c|c|c|c|}
    \hline
    Буква&Индекс буквы в словаре&Код&Длина\\    
 \hline I&73&01001001&8\\  \hline n&110&001101110&9\\  \hline \_&95&001011111&9\\  \hline o&111&001101111&9\\  \hline r&114&001110010&9\\  \hline d&100&001100100&9\\  \hline e&101&001100101&9\\  \hline r&114&001110010&9\\  \hline \_&95&001011111&9\\  \hline t&116&001110100&9\\  \hline o&111&001101111&9\\  \hline \_&95&001011111&9\\  \hline g&103&001100111&9\\  \hline e&101&001100101&9\\  \hline t&116&001110100&9\\  \hline \_&95&001011111&9\\  \hline w&119&001110111&9\\  \hline h&104&001101000&9\\  \hline er&262&100000110&9\\  \hline e&101&001100101&9\\  \hline \_&95&001011111&9\\  \hline y&121&001111001&9\\  \hline o&111&001101111&9\\  \hline u&117&001110101&9\\  \hline \_w&271&100001111&9\\  \hline a&97&001100001&9\\  \hline n&110&001101110&9\\  \hline t\_&270&100001110&9\\  \hline to&265&100001001&9\\  \hline \_g&267&100001011&9\\  \hline o&111&001101111&9\\  \hline ,&44&000101100&9\\  \hline \_y&276&100010100&9\\  \hline ou&278&100010110&9\\  \hline \_&95&001011111&9\\  \hline f&102&001100110&9\\  \hline i&105&001101001&9\\  \hline r&114&001110010&9\\  \hline s&115&001110011&9\\  \hline t\_&270&100001110&9\\  \hline h&104&001101000&9\\  \hline a&97&001100001&9\\  \hline v&118&001110110&9\\  \hline e\_&275&100010011&9\\  \hline to\_&284&100011100&9\\  \hline l&108&001101100&9\\  \hline e&101&001100101&9\\  \hline av&297&100101001&9\\  \hline e\_&275&100010011&9\\  \hline wh&272&100010000&9\\  \hline ere&274&100010010&9\\  \hline \_yo&288&100100000&9\\  \hline u\_&279&100010111&9\\  \hline a&97&001100001&9\\  \hline r&114&001110010&9\\  \hline e&101&001100101&9\\  \hline 
    \end{longtable}
\end{center}

Итого, суммарная длина равна 503 бита. Больше чем у предыдущих алгоритмов из-за относительно большого алфавита, на текстах, размер которых значительно больше, должен работать гораздо эффективнее.

\subsection{Алгоритм PPMA}
\begin{center}
    \begin{longtable}{|c|c|c|p{3cm}|c|}
    \hline
    Буква&Контекст&Длины контекстов&Вероятность&Вероятность новой буквы\\    
    \hline I&-&0&1&1 / 256\\  \hline n&-&1&1 / 2&1 / 255\\  \hline \_&-&2&1 / 3&1 / 254\\  \hline o&-&3&1 / 4&1 / 253\\  \hline r&-&4&1 / 5&1 / 252\\  \hline d&-&5&1 / 6&1 / 251\\  \hline e&-&6&1 / 7&1 / 250\\  \hline r&-&7&&1 / 8\\  \hline \_&r&1;7&1 / 2&1 / 8\\  \hline t&\_&1;8&1 / 2 * 1 / 9&1 / 249\\  \hline o&-&10&&1 / 11\\  \hline \_&o&1;9&1 / 2&1 / 5\\  \hline g&\_&2;9&1 / 3 * 1 / 10&1 / 248\\  \hline e&-&13&&1 / 14\\  \hline t&e&1;12&1 / 2&1 / 13\\  \hline \_&t&1;13&1 / 2&3 / 14\\  \hline w&\_&3;11&1 / 4 * 1 / 12&1 / 247\\  \hline h&-&17&1 / 18&1 / 246\\  \hline e&-&18&&2 / 19\\  \hline r&e&2&&1 / 3\\  \hline e&er&1;1;15&1 / 2 * 1 / 2&3 / 16\\  \hline \_&e&3;16&1 / 4&4 / 17\\  \hline y&\_&4;16&1 / 5 * 1 / 17&1 / 245\\  \hline o&-&23&&1 / 12\\  \hline u&o&2;16&1 / 3 * 1 / 17&1 / 244\\  \hline \_&-&25&&5 / 26\\  \hline w&\_&5&&1 / 6\\  \hline a&\_w&1;0;26&1 / 2 * 1 * 1 / 27&1 / 243\\  \hline n&-&28&&1 / 29\\  \hline t&n&1;23&1 / 2&1 / 12\\  \hline \_&t&2&&1 / 3\\  \hline t&t\_&1;4&1 / 2&1 / 5\\  \hline o&\_t&1&&1 / 2\\  \hline \_&\_to&1&&1 / 2\\  \hline g&\_to\_&1&&1 / 2\\  \hline o&\_to\_g&1;0;0;0;0;31&1 / 2 * 1 * 1 * 1 * 1&1 / 8\\  \hline ,&o&4;24&1 / 5 * 1 / 25&1 / 242\\  \hline \_&-&37&&4 / 19\\  \hline y&\_&8&&1 / 9\\  \hline o&\_y&1&&1 / 2\\  \hline u&\_yo&1&&1 / 2\\  \hline \_&\_you&1&&1 / 2\\  \hline f&\_you\_&1;0;0;0;7;26&1 / 2 * 1 * 1 * 1 * 1 / 8 * 1 / 27&1 / 241\\  \hline i&-&43&1 / 44&1 / 240\\  \hline r&-&44&&1 / 15\\  \hline s&r&3;30&1 / 4 * 1 / 31&1 / 239\\  \hline t&-&46&&4 / 47\\  \hline \_&t&4&&2 / 5\\  \hline h&t\_&2;6;30&1 / 3 * 1 / 7&1 / 31\\  \hline a&h&1;45&1 / 2&1 / 46\\  \hline v&a&1;48&1 / 2 * 1 / 49&1 / 238\\  \hline e&-&51&&1 / 13\\  \hline \_&e&4&&1 / 5\\  \hline t&e\_&1;9&1 / 2&1 / 5\\  \hline o&\_t&2&&2 / 3\\  \hline \_&\_to&2&&2 / 3\\  \hline l&\_to\_&2;0;0;10;34&1 / 3 * 1 * 1 * 1 / 11 * 1 / 35&1 / 237\\  \hline e&-&57&&5 / 58\\  \hline a&e&5;35&1 / 6&1 / 18\\  \hline v&a&2&&1 / 3\\  \hline e&av&1&&1 / 2\\  \hline \_&ave&1&&1 / 2\\  \hline w&ave\_&1;0;1;8&1 / 2 * 1 * 1 / 2&2 / 9\\  \hline h&\_w&2&&1 / 3\\  \hline e&\_wh&1&&1 / 2\\  \hline r&\_whe&1&&1 / 2\\  \hline e&\_wher&1&&1 / 2\\  \hline \_&where&1&&1 / 2\\  \hline y&here\_&1&&1 / 2\\  \hline o&ere\_y&1&&1 / 2\\  \hline u&re\_yo&1&&1 / 2\\  \hline \_&e\_you&1&&1 / 2\\  \hline a&\_you\_&2;0;0;0;11;45&1 / 3 * 1 * 1 * 1 * 1 / 12&3 / 46\\  \hline r&a&3;69&1 / 4&1 / 14\\  \hline e&r&5&&1 / 3\\  \hline 
    \end{longtable}
\end{center}

Итого, суммарная длина записи равна 411.

\newpage

\subsection{Сравнение всех алгоритмов}

В следующей таблице можно увидеть результат сравнения алгоритмов кодирования.

\begin{center}
    \begin{longtable}{|c|c|c|}
       \hline
       Алгоритм&Длина кода \\
       \hline
       Двупроходный алгоритм Хаффмена& 483 бита \\
       \hline
       Адаптивное арифметическое кодирование& 432 бита \\
       \hline
       Нумерационное кодирование & 504 бита \\
       \hline
       Алгоритм LZ-77 & 467 бит \\
       \hline
       Алгоритм LZW & 503 бита \\
       \hline
       Алгоритм PPMA & 411 бит \\
       \hline       
    \end{longtable}
\end{center}
